﻿namespace Leetcode.N0322.V2;

public class Solution
{
    public int CoinChange(int[] coins, int amount)
    {

        coins = coins.OrderByDescending(_ => _).ToArray();
        var minCount = int.MaxValue;
        var cache = new Dictionary<int, IDictionary<int, int>>();
        for (int i = 0; i < coins.Length; i++)
        {
            cache.Add(i, new Dictionary<int, int>());
        }

        this.CoinChange(coins, amount, 0, 0, ref minCount, cache);
        return minCount == int.MaxValue ? -1 : minCount;
    }

    public void CoinChange(int[] coins, int amount, int index, int preCount, ref int minCount, IDictionary<int, IDictionary<int, int>> cache)
    {
        if (amount == 0)
        {
            minCount = Math.Min(preCount, minCount);
            return;
        }

        if (index >= coins.Length)
        {
            return;
        }

        if (cache.ContainsKey(index))
        {
            if (!cache[index].ContainsKey(amount))
            {
                cache[index].Add(amount, int.MaxValue);
            }

            if (cache[index][amount] <= preCount)
            {
                return;
            }
        }

        for (var curCount = amount / coins[index]; curCount >= 0 && (preCount + curCount) < minCount; curCount--)
        {
            this.CoinChange(coins, amount - coins[index] * curCount, index + 1, preCount + curCount, ref minCount, cache);
        }
        cache[index][amount] = Math.Min(cache[index][amount], preCount);
    }
}
